#include <stdio.h>

#define N 1005
int dp[N][N];
char ans[N];

int getStrLen(char *str)
{
    int i = 0;
    for (; str[i] != '\0'; i++)
        ;
    return i;
}

char *lcs(char *s1, char *s2)
{
    int n = getStrLen(s1), m = getStrLen(s2);
    if (n >= N || m >= N)
        return NULL;
    int max = 0, max_addr = 0;
    for (int i = 0; i <= n; i++)
        dp[i][0] = 0;
    for (int j = 0; j <= m; j++)
        dp[0][j] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (s1[i - 1] == s2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > max)
                {
                    max = dp[i][j];
                    max_addr = i;
                }
            }
            else
                dp[i][j] = 0;
        }
    ans[max_addr] = '\0';
    for (int i = 0; i < max; i++)
        ans[i] = s1[max_addr - i - 1];
    return ans;
}

int main()
{
    char *s1 = "aabaaa";
    char *s2 = "baab";
    printf("%s", lcs(s1, s2));
}